package com.cat.chapter052;

import java.util.Arrays;

/**
 * @author cat
 * @description https://leetcode.cn/problems/sum-of-subarray-minimums/
 * @create 2025/7/23 14:48
 * @since JDK17
 */

public class Solution03 {
    static int N = ((int) (3e4 + 10)), M = ((int) (1e9 + 7));
    static int[] stack = new int[N], ans = new int[N];
    public int sumSubarrayMins(int[] arr) {
        long res = 0;
        int n = arr.length, cur, r = 0, left;
        Arrays.fill(ans, 0, n, -1);
        for (int i = 0; i < n; i++) {   // 找到右边比其小的数字
            while (r > 0 && arr[stack[r - 1]] > arr[i]) {
                cur = stack[--r];
                left = r == 0 ? -1 : stack[r - 1];
                res = (res + (long) ((cur - left) * (i - cur)) * arr[cur]) % M;
            }
            stack[r++] = i;
        }

        while (r > 0) {
            cur = stack[--r];
            left = r == 0 ? -1 : stack[r - 1];
            res = (res + (long) ((cur - left) * (n - cur)) * arr[cur]) % M;
        }

        return ((int) (res % M));
    }
}
